package com.leetcode.math;

import java.util.Arrays;

public class CountDigits {

    private int minSum;
    private int maxSum;
    private static final int MOD = (int)1e9 + 7;

    public static void main(String[] args) {

    }

    public int count(String num1, String num2, int min_sum, int max_sum) {
        int res = 0;
        this.minSum = min_sum;
        this.maxSum = max_sum;
        res = count(num2) - count(num1) + MOD;
        int sum = 0;
        for (char c : num1.toCharArray()) {
            sum += c - '0';
        }
        if (sum >= min_sum && sum <= maxSum) {
            res++;
        }
        return res % MOD;
    }

    public int count(String str) {
        char[] strArr = str.toCharArray();
        int n = strArr.length;
        int[][] mem = new int[n][Math.min(n*9,  maxSum) + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(mem[i], -1);
        }
        return f(strArr, mem, 0, 0, true);
    }

    public int f(char[] strArr, int[][] mem, int ind, int sum, boolean isLimit) {
        if (sum > maxSum) {
            return 0; // 非数字
        }
        if(ind == strArr.length) {
            return sum >= minSum ? 1:0;
        }
        if(!isLimit && mem[ind][sum] != -1) {
            return mem[ind][sum];
        }
        int res = 0;
        int up = isLimit ? strArr[ind] - '0' : 9;
        for (int d = 0; d <= up; d++) {
            res = (res + f(strArr, mem, ind + 1,
                    sum + d, isLimit && d == up)) % MOD;
        }
        if (!isLimit) {
            mem[ind][sum] = res;
        }
        return res;
    }
}
